package Algorithm.Sort;

//插入排序,平均时间复杂度为O(N2)
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 9, 8, 7, 26, 13, 42, 36, 99};
        printArray(arr);
        function(arr);
        printArray(arr);
    }

    public static void function(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //从后往前依次比较，找到合适的位置之后就确定了。
            for (int j = i + 1; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                } else {
                    //break只会退出当前循环，所以如果待排序数组的第一位比一排序的最大一位还打，那这个数就不需要排序，直接放在一排序的最后一个就行了。
                    break;
                }
            }
        }
    }

    //工具方法，顺序打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }


}
